﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0022_IsPalindromeList
    {
        // 回文链表

        // 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

        //提示：
        //链表中节点数目在范围[1, 10^5] 内
        //0 <= Node.val <= 9

        //进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

        public void Test()
        {
            var l1 = new ListNode(1)
            {
                next = new ListNode(3)
                {
                    next = new ListNode(2)
                    {
                        next = new ListNode(3)
                        {
                            next = new ListNode(1)
                        }
                    }
                }
            };
            Console.WriteLine(IsPalindrome(l1));
            Console.Read();
        }

        // 快慢指针找到中间节点+反转后半段链表，再循环比较链表
        public bool IsPalindrome(ListNode head)
        {
            ListNode fast = head, slow = head;
            //通过快慢指针找到中点
            while (fast != null && fast.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
            }
            //如果fast不为空，说明链表的长度是奇数个
            if (fast != null)
            {
                slow = slow.next;
            }
            //反转后半部分链表
            slow = Reverse(slow);

            fast = head;
            while (slow != null)
            {
                //然后比较，判断节点值是否相等
                if (fast.val != slow.val)
                    return false;
                fast = fast.next;
                slow = slow.next;
            }
            return true;
        }
        //反转链表
        public ListNode Reverse(ListNode head)
        {
            ListNode prev = null;
            while (head != null)
            {
                ListNode next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }

        // 入栈并记录总长，根据长度循环出栈比较链表值
        public bool IsPalindrome1(ListNode head)
        {
            if (head == null)
                return true;
            ListNode temp = head;
            var stack = new Stack<int>();
            //链表的长度
            int len = 0;
            //把链表节点的值存放到栈中
            while (temp != null)
            {
                stack.Push(temp.val);
                temp = temp.next;
                len++;
            }
            //len长度除以2
            len >>= 1;
            //然后再出栈
            while (len-- >= 0)
            {
                if (head.val != stack.Pop())
                    return false;
                head = head.next;
            }
            return true;
        }

        // 递归
        ListNode temp;
        public bool IsPalindrome2(ListNode head)
        {
            temp = head;
            return Check(head);
        }
        private bool Check(ListNode head)
        {
            if (head == null)
                return true;
            bool res = Check(head.next) && (temp.val == head.val);
            temp = temp.next;
            return res;
        }
    }
}
